home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / general / modelers / geomview / source.lha / Geomview / src / lib / oogl / wa / fsaparse.y < prev    next >
Encoding:
Text File  |  1993-04-08  |  3.7 KB  |  217 lines
  1. /*
  2.  * fsaparse.y
  3.  *
  4.  *    Yacc grammar for parsing word-acceptor automata in the format
  5.  *    described by DEAGL ("Data Exchange for Automata and Groups
  6.  *    Language").
  7.  *
  8.  *    This grammar does NOT recognize the entire language described
  9.  *    in DEAGL.  The main function is fsaparse(), defined below.  See
  10.  *    the comments in that function for more info.
  11.  *
  12.  *    mbp Sat Mar 23 21:56:30 1991
  13.  *    mbp@thales.urich.edu
  14.  */
  15.  
  16. %{
  17.  
  18. #include <stdio.h>
  19. #include "wa.h"
  20. #include "yystype.h"
  21. #include "y.tab.h"
  22.  
  23. #define MAXSTATES 100
  24. #define MAXGENS 128
  25.  
  26. static char copyright[] =
  27.   "Copyright (C) 1991 Mark B. Phillips, The Geometry Center";
  28.  
  29. static int adj[MAXSTATES];
  30. static int adj_index = 0;
  31. static int install_adjacency();
  32.  
  33. static wa *fsa;
  34.  
  35. %}
  36.  
  37. %start fsa_file
  38.  
  39. %token <i> FORMAT FSA STATES SYMBOLS BFS MIN VARIABLES ALPHABET START ATABLE INVERSES INV LEFT_BRACE RIGHT_BRACE LEFT_PAREN RIGHT_PAREN SEMICOLON PERCENT INT EQUAL
  40.  
  41. %token <s> STRING
  42.  
  43. %token <d> REAL
  44.  
  45. %type <i> start_states
  46.  
  47. %%
  48. fsa_file    : FORMAT REAL fsa_format
  49.         ;
  50.  
  51. fsa_format    : FSA
  52.           LEFT_BRACE
  53.           states
  54.           symbols
  55.           fsa_characteristics
  56.           info_items
  57.           PERCENT
  58.           fsa_table
  59.           RIGHT_BRACE
  60.             { return(0); }
  61.         ; 
  62.  
  63. states        : STATES INT
  64.             {
  65.               fsa->nstates = $2;
  66.               fsa->action =
  67.             (int**)malloc((fsa->nstates+1)*sizeof(int*));
  68.             }
  69.         ;
  70.  
  71. symbols        : SYMBOLS INT
  72.             {
  73.               int i,j;
  74.               fsa->ngens = $2;
  75.               for (i=0; i<=fsa->nstates; ++i) {
  76.             fsa->action[i] =
  77.               (int*)malloc((fsa->ngens+1)*sizeof(int));
  78.             for (j=0; j<=fsa->ngens; ++j)
  79.               fsa->action[i][j] = 0;
  80.               }
  81.               fsa->genlist=(char**)malloc(fsa->ngens*sizeof(char*));
  82.               for (i=0; i<fsa->ngens; ++i)
  83.             fsa->genlist[i] = "";
  84.             }
  85.         ;
  86.  
  87. fsa_characteristics
  88.         : fsa_characteristic
  89.         | fsa_characteristic fsa_characteristics
  90.         ;
  91.  
  92.  
  93. fsa_characteristic
  94.         : BFS
  95.           | MIN
  96.         | VARIABLES INT
  97.         ;
  98.  
  99.  
  100. info_items    : info_item
  101.         | info_item info_items
  102.         ;
  103.  
  104. info_item    : alphabet
  105.           | start_states
  106.             {
  107.               fsa->start= $1;
  108.             }
  109.         ;
  110.  
  111. alphabet    : ALPHABET LEFT_BRACE symbol_names RIGHT_BRACE
  112.         ;
  113.  
  114. symbol_names    : symbol_name
  115.           | symbol_names symbol_name
  116.         ;
  117.  
  118. symbol_name    : INT EQUAL STRING
  119.             {
  120.               fsa->genlist[$1-1] =
  121.             (char*)malloc((strlen($3)+1)*sizeof(char));
  122.               strcpy(fsa->genlist[$1-1], $3);
  123.             }
  124.         ;
  125.  
  126. start_states    : START LEFT_BRACE INT RIGHT_BRACE
  127.             { $$ = $3; }
  128.         | START LEFT_BRACE INT int_list RIGHT_BRACE
  129.             { $$ = $3; }
  130.         
  131.         ;
  132.  
  133. int_list    : INT
  134.         | INT int_list
  135.         ;
  136.  
  137.  
  138. fsa_table    : ATABLE acstates
  139.         | ATABLE
  140.         ;
  141.  
  142. acstates    : acstate
  143.         | acstate acstates
  144.         ;
  145.  
  146. acstate        : INT STRING adjacency SEMICOLON
  147.           { install_adjacency($1); adj_index = 0; }
  148.         ;
  149.  
  150. adjacency    : INT
  151.           {
  152.             adj[adj_index++] = $1;
  153.           }
  154.         | adjacency INT
  155.           {
  156.             adj[adj_index++] = $2;
  157.           }
  158.         ;
  159.  
  160.  
  161. %%
  162.  
  163. yyerror(s)
  164. char *s;
  165. {
  166.   printf("yyerror: %s\n");
  167. }
  168.  
  169. static int
  170.   install_adjacency(n)
  171. int n;
  172. {
  173.   int i;
  174.  
  175.   for (i=0; i<adj_index; ++i)
  176.     fsa->action[n][i+1] = adj[i];
  177. }
  178.  
  179. parse_init(f)
  180.      wa *f;
  181. {
  182.   fsa = f;
  183.  
  184.   fsa->fail = fsa->state = 0;
  185. }
  186.  
  187. /*-----------------------------------------------------------------------
  188.  * Function:    fsaparse
  189.  * Description:    parse a .wa file into an wa struct
  190.  * Args  IN:    fp: .wa file pointer
  191.  *      OUT:    *fsa: the resulting fsa struct
  192.  * Returns:    1 for success, 0 for error
  193.  * Author:    mbp
  194.  * Date:    Sat Mar 23 21:47:04 1991
  195.  * Notes:    Does not recognize the full grammar defined by
  196.  *        "Data Exchange for Automatic Groups".  Only recognizes
  197.  *        files of the form used by several examples I was
  198.  *        using at the time I wrote this.  I think, but am not
  199.  *        at all sure, that this includes all word-acceptor
  200.  *        automata.
  201.  */
  202. int
  203.   fsaparse(fp, fsa)
  204. FILE *fp;
  205. wa *fsa;
  206. {
  207.   extern FILE *yyin;
  208.   int ret;
  209.  
  210.   parse_init(fsa);
  211.  
  212.   yyin = fp;
  213.   ret = yyparse();
  214.  
  215.   return(ret ==0);
  216. }
  217.